import com.sun.javafx.collections.MappingChange;
import org.omg.CORBA.INTERNAL;

import java.util.*;

/**
 * @author:gao
 * @date:2020/6/12
 * @time:12:29
 * @version:0.0.1
 * @description:none
 */


//15 三数之和 不让有重复
class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;
        //通过排序，然后按照序号从小到大进行遍历，防止重复
        Arrays.sort(nums);
        int last_i = Integer.MIN_VALUE;
        for(int left=0;left<nums.length-2;left++){
            if(last_i==nums[left]){
                continue;
            }else{
                last_i = nums[left];
            }
            int mid = left+1;
            int right = nums.length-1;
            int last_mid = Integer.MAX_VALUE;
            int last_right = Integer.MAX_VALUE;
            boolean change_mid = false;
            boolean change_r = false;
            //三个数，固定一个，用双指针向中间逼近
            while (mid<right){
                if(change_mid&&last_mid==nums[mid]){
                    mid++;
                    change_mid = true;
                    continue;
                }else{
                    last_mid=nums[mid];
                    change_mid =false;
                }
                if(change_r&&last_right==nums[right]){
                    right--;
                    change_r=true;
                    continue;
                }else{
                    last_right=nums[right];
                    change_r=false;
                }
               int sum = nums[left]+nums[mid]+nums[right];
                if(sum>0){
                    right--;
                    change_r = true;
                    change_mid =false;
                }else if(sum<0){
                    mid++;
                    change_mid =true;
                    change_r =false;
                }else{
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[left]);
                        list.add(nums[mid]);
                        list.add(nums[right]);
                        ans.add(list);
                        right--;
                        mid++;
                        change_mid =true;
                        change_r = true;
                }
            }
        }
        return ans;
    }

}